package com.sicheng.lc.周赛.分类.秒杀子数组类题目基本原理_前缀和_滑动窗体_数论;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/11 11:12
 */
public class 连续的子数组和 {
    //https://leetcode.cn/problems/continuous-subarray-sum/
    public boolean checkSubarraySum(int[] nums, int k) {
        HashMap<Integer, List<Integer>> map = new HashMap<>((int) 1e6);
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = (sum + nums[i]) % k;
            if (sum == 0 && i + 1 >= 2) {
                return true;
            }
            List<Integer> lens = map.computeIfAbsent((int) sum, m -> new ArrayList<>(10));
            if (!lens.isEmpty() && i + 1 - lens.get(0) >= 2) {
                return true;
            }
            lens.add(i + 1);
        }
        return false;
    }
}
